package com.mc.search;

public class RedBlackBST<Key extends Comparable<Key>,Value> {
	private final boolean RED = true;
	private final boolean BLACK = false;
	
	private Node root;

	private boolean isRed(Node node){
		if(node==null)return false;
		return node.color == RED;
	}
	public int size(){
		return size(root);
	}
	private int size(Node node){
		if(node==null)return 0;
		return node.N;
	}
	private Node rotateLeft(Node node){
		Node temp = node.right;
		node.right = temp.left;
		temp.left = node;
		temp.color = node.color;
		node.color = RED;
		temp.N = node.N;
		node.N = 1+size(node.left)+size(node.right);
		return temp;
	}
	private Node rotateRight(Node node){
		Node temp = node.left;
		node.left = temp.right;
		temp.right = node;
		temp.color = node.color;
		node.color = RED;
		temp.N = node.N;
		node.N = 1+size(node.left)+size(node.right);
		return temp;
	}
	private void flipColors(Node node){
		node.color = RED;
		node.left.color = BLACK;
		node.right.color = BLACK;
	}
	public void put(Key key, Value val){
		root = put(root,key,val);
		root.color = BLACK;
	}
	private Node put(Node node,Key key,Value val){
		if(node==null)
			return new Node(key,val,1,RED);
		int cmp = key.compareTo(node.key);
		if(cmp<0)node.left = put(node.left,key,val);
		else if(cmp>0)node.right = put(node.right,key,val);
		else node.val = val;
		
		if(isRed(node.right)&&!isRed(node.left))
			node = rotateLeft(node);
		if(isRed(node.left)&&isRed(node.left.left))
			node = rotateRight(node);
		if(isRed(node.left)&&isRed(node.right))
			flipColors(node);
		node.N = size(node.left)+size(node.right)+1;
		return node;
	}
	private class Node{
		Key key;
		Value val;
		Node left,right;
		int N;
		boolean color;
		public Node(Key key,Value val,int n,boolean color){
			this.key = key;
			this.val = val;
			this.N = n;
			this.color = color;
		}
	}
}
